//
//  ProblemOffer07.swift
//  TestProject
//
//  Created by 武侠 on 2021/7/6.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 剑指 Offer 07. 重建二叉树
 输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

 例如，给出
     前序遍历 preorder = [3,9,20,15,7]
     中序遍历 inorder = [9,3,15,20,7]
     返回如下的二叉树：

         3
        / \
       9  20
         /  \
        15   7
 限制：0 <= 节点个数 <= 5000
 */
@objcMembers class ProblemOffer07: NSObject {
    func solution() {
        let node = buildTree([3,9,8,20,15,7],
                             [8,9,3,15,20,7])
        print(printNodeTree(node))
    }
    func buildTree(_ preorder: [Int], _ inorder: [Int]) -> TreeNode? {
        if preorder.count == 0 {
            return nil
        }
        return buildTreeBFS(preorder, 0, preorder.count-1, inorder, 0, inorder.count-1)
    }
    
    /*
     前序遍历 preorder = [3,9,20,15,7]
     中序遍历 inorder  = [9,3,15,20,7]
     [3,9,8,20,15,7],
     [8,9,3,15,20,7]
     */
    func buildTreeBFS(_ preorder: [Int], _ prs: Int, _ pre: Int, _ inorder: [Int], _ ins: Int, _ ine: Int) -> TreeNode? {
        print(prs, pre, ins, ine)
        if pre < prs || ine < ins {
            return nil
        }
        let root = TreeNode(preorder[prs])
        if prs == pre {
            return root
        }
        
        var len = 0
        for i in ins...ine {
            if inorder[i] == preorder[prs] {
                break
            }
            len += 1
        }
        print(len)
        root.left  = buildTreeBFS(preorder, prs + 1, prs + len, inorder, ins, ins + len - 1)
        root.right = buildTreeBFS(preorder, prs + 1 + len, pre, inorder, ins + 1 + len, ine)
        
        return root
    }
}
